package cxydmmszl.tmp.t3;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.HashSet;

/**
 * <li style="color: red;">Prob</li>
 * 一种消息接收并打印的结构设计
 * <li style="color: green;">Desc</li>
 * 已知一个消息流会不断地吐出整数 1∼N，但不一定按照顺序吐出。
 * 如果上次打印的数为 i，那么当 i+1 出现时，请打印i+1及其之后接收过的并且连续的所有数，
 * 直到 1∼N 全部接收并打印完，请设计这种接收并打印的结构。
 * <br/><br/>[要求]<br/>
 * 消息流最终会吐出全部的 1∼N，当然最终也会打印完所有的 1∼N，要求接收和打印 1∼N 的整个过程，时间复杂度为 O(N)。
 * <br/><br/>备注：<br/>
 * 1⩽N⩽10^5<br/>
 * 保证输入的是一个 1∼N 的排列
 * <li style="color: green;">Input</li>
 * 第一行一个整数 N。
 * 接下来一行有 N 个整数。保证输入是一个 1 到 N 的排列
 * <li style="color: green;">Output</li>
 * 输出N行，每行两个数。
 * 为了检验输出的正确性，请在输出当前打印的数字之后输出此时最后一个加入的元素。
 * <li style="color: blue;">Link</li> CD79
 *
 * @author habitplus
 * @since 2021-11-02 13:41
 */
public class Main {
    static final StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
        } catch (IOException e) {
            throw new RuntimeException("Input is invalid!");
        }
        return (int) st.nval;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }

        print(arr);
    }

    private static void print(int[] arr) {
        if (arr == null || arr.length < 1) return;

        int cur = 0;
        StringBuilder sb = new StringBuilder();
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == cur + 1) {
                sb.append(arr[i]).append(" ").append(arr[i]).append("\n");
                cur++;
                while (set.contains(cur+1)) {
                    cur++;
                    sb.append(cur).append(" ").append(arr[i]).append("\n");
                    set.remove(cur);
                }
            } else {
                set.add(arr[i]);
            }
        }
        System.out.print(sb.toString());
    }
}
